package cn.corgy.demo;

import java.util.Stack;

public class demo1 {
    static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

    public static int[] reversePrint(ListNode head) {
        Stack<Integer> stack = new Stack();
        ListNode curr = head;//指针
        while (curr != null) {
            stack.push(curr.val);
            curr = curr.next;
        }
        int size = stack.size();
        int[] ints = new int[stack.size()];
        for (int i = 0; i < size; i++) {
            ints[i] = stack.pop();

        }
        return ints;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{1, 6, 9, 3, 5};
        System.out.println(rob(nums));
    }


    public static int rob(int[] nums) {
        return rec_opt(nums, nums.length - 1);
    }

    static int rec_opt(int[] nums, int i) {
        if (i == 1) {
            return Math.max(nums[0], nums[1]);
        } else if (i == 0) {
            return nums[0];
        } else {
            int a = rec_opt(nums, i - 2) + nums[i];
            int b = rec_opt(nums, i - 1);
            return Math.max(a, b);
        }
    }


}
